Rangefinding, the measurement of the 3D profile of an object or scene, is a critical component for many robotic applications. Of the many rangefinding techniques that have been developed, see P. J. Besl. Range Imaging Sensors. Research Publication GMR-6090, General Motors Research Laboratories, Mar. 15, 1988, lightstripe rangefinding remains one of the most widely used and reliable methods available. In a conventional lightstripe system, a complete range map is obtained via the step-and-repeat process of projecting a stripe, grabbing a camera image, extracting the projected stripe positions, and stepping the stripe until an entire scene has been scanned. Though practical, the speed of sampling range data with this conventional technique is severely limited.
FIG. 4 shows the geometrical principle on which a lightstripe rangefinder operates. The scene is illuminated with a vertical plane of light. The light is intercepted by an object surface in the path of the beam and, when seen by a video camera placed to the left of the light source, appears as a stripe which follows the surface contour of objects in the scene.
Range data along the contour can be calculated easily using the principle of triangulation. In FIG. 4, the equation of the plane of light L is known because the projection angle .theta. is controlled. The line of sight R for each point p on the image of the stripe can also be determined by tracing a line from the image focal point f.sub.p through p. The intersection of the ray R with the plane L uniquely determines the three-dimensional position of P on the surface corresponding to p.
A conventional step-and-repeat rangefinder collects range data for an entire scene sequentially--iterating the process of fixing the stripe on the scene, taking a picture, and processing the resultant image until the entire scene has been scanned.
Though practical, the speed of sampling range data by the conventional light stripe technique is severely limited. Assume that a video camera image has N rows. Since from one image at each step there can be obtained up to N data points, the maximum speed of sampling being S.sub.max =N/T.sub.f is the time required to acquire and process an image frame. Typically, N ranges between 256 and 512 samples and T.sub.f ranges between 1/30 second and 1/10 second. Thus, sampling speeds of camera based systems are limited to EQU S.sub.max .apprxeq.2.5k-15ksamples/second.
The algorithm used by a lightstripe rangefinder implemented with the present invention is based on the lightstripe ranging technique in a manner described by Sato, see Y. Sato, K. Araki, and S. Parthasarathy. High speed rangefinder. SPIE, 1987, and Kida, see T. Kida, K. Sato, and S. Inokuchi. Realtime range imaging sensor. In Proceedings 5th Sensing Forum, pages 91-95, April 1988. In Japanese.
The lightstripe rangefinder of the present invention utilizes a photosensitive array of cells on an integrated circuit to derive range information from a structured light source. Sampling speeds of ##EQU1## can be achieved. M.sup.2 represents the total number of sensors in the overall system, and T.sub.s represents the time to acquire data.
One of the aspects of the present invention which accomplish this several orders of magnitude sampling speed increase is the ability to sweep the lightstripe continuously across a scene, with the photosensitive array receiving information from the sweeping lightstripe and processing this information.
The present invention is directed to an array of cells, each of which provides for the ability to integrate memory, and processing into each cell. Examples of this class of chip exist and include commercial CCD image chips, the Xerox Optical Mouse, see R. F. Lyon. The Optical Mouse, and an Architectural Methodology for Smart Digital Sensors. Technical Report VLSI-81-1, Xerox Palo Alto research Center, August 1981, Mead's Artificial Retina, see M. A. Sivilotti, M. A. Mahowald, and C. A. Mead. Real-time visual computations using analog cmos processing arrays. In P. Losleben, editor, Advanced research in VLSI--Proceedings of the 1987 Stanford Conference, pages 295-312. The MIT Press, 1987, and an Optical Position Encoder done at the CSEM in Switzerland, see P. Aubert and H. Oguey. An application specific integrated circuit (asic) with cmos-compatible light sensors for an optical position encoder. In IEEE 1987 Custom Integrated Circuits Conference, pages 712-716, IEEE, May 1987. However, none of these have the one-to-one relationship existing between the sensor, processing and memory circuitry necessary to achieve the desired results.